We consider a two-sided market under incomplete preference lists with ties, where\r\nthe goal is to find a maximum size stable matching. The problem is APX-hard, and a\r\n3/2-approximation was given by McDermid [1]. This algorithm has a non-linear running\r\ntime, and, more importantly needs global knowledge of all preference lists. We present\r\na very natural, economically reasonable, local, linear time algorithm with the same ratio,\r\nusing some ideas of Paluch [2]. In this algorithm every person make decisions using only\r\ntheir own list, and some information asked from members of these lists (as in the case of\r\nthe famous algorithm of Gale and Shapley). Some consequences to the Hospitals/Residents\r\nproblem are also discussed.
Loading....